{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Production Orders\n",
    "## Problem Definition\n",
    "The firm H.G. Welds, dedicated to welding components for the automotive sector, has received five orders (P1, P2, P3, P4, P5), which have to be carried out. To meet these orders, the company has five welding machines available (M1, M2, M3, M4,M5). Each machine can carry out every task at the cost shown in the table below. The problem consists in determining optimum allocation which minimises the total cost of carrying out orders by assuming that each machine can do only one order and that all the orders must be carried out.\n",
    "\n",
    "| Order/Machine | M1  | M2  | M3  | M4  | M5  |\n",
    "|---------------|-----|-----|-----|-----|-----|\n",
    "| P1            | 16  | 4   | 9   | 5   | 6   |\n",
    "| P2            | 2   | 14  | 7   | 5   | 13  |\n",
    "| P3            | 8   | 10  | 3   | 12  | 11  |\n",
    "| P4            | 3   | 7   | 6   | 10  | 5   |\n",
    "| P5            | 3   | 6   | 8   | 11  | 7   |\n",
    "\n",
    "**Formulate an integer linear programming model to determine the optimum allocation plan.**\n",
    "**Assume that processing each order on each machine requires an average preparation cost of 10 units. How is the model in the former sector amended?**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem model\n",
    "This is an instance of an assignment problem.\n",
    "\n",
    "### Decision variables\n",
    "\n",
    "$x_{ij} = 1$ if Machine Mi carries out order Pj, and 0 otherwise;\n",
    "\n",
    "### Objective function\n",
    "It represents the total cost of carrying out tasks, and can be expressed as the sum of all the costs $c_{ij}$ which are the elements of the cost matrix in the table. Note that the rows in the table represent the costs associated to a production order, whereas in our matrix, each row represents the costs associated to a machine, so we need to **transpose** the table provided:\n",
    "\n",
    "$C = \\begin{bmatrix}\n",
    "c_{11} & c_{12} & \\cdots & c_{1n} \\\\\n",
    "c_{21} & c_{22} & \\cdots & c_{2n} \\\\\n",
    "\\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "c_{m1} & c_{m2} & \\cdots & c_{mn} \\\\\n",
    "\\end{bmatrix}\n",
    "= \\begin{bmatrix}\n",
    "16 & 2 & 8 & 3 & 3 \\\\\n",
    "4 & 14 & 10 & 7 & 6 \\\\\n",
    "9 & 7 & 3 & 6 & 8 \\\\\n",
    "5 & 5 & 12 & 10 & 11 \\\\\n",
    "6 & 13 & 11 & 5 & 7 \\\\\n",
    "\\end{bmatrix}$\n",
    "\n",
    "Now, the objective function is to **minimize costs**, therefore:\n",
    "\n",
    "$\\min z = \\sum_i\\sum_j{x_{ij}*c_{ij}} = 16x_{11} + 2x_{12} + 8x_{13} + 3x_{14} + 3x_{15} + ...$\n",
    "\n",
    "$... + 4x_{21} + 14x_{22} + 10x_{23} + 7x_{24} + 6x_{25} + ...$\n",
    " \n",
    "$... + 9x_{31} + 7x_{32} + 3x_{33} + 6x_{34} + 8x_{35} + ...$\n",
    "\n",
    "$... + 5x_{41} + 5x_{42} + 12x_{43} + 10x_{44} + 11x_{45} + ...$ \n",
    "\n",
    "$... + 6x_{51} + 13x_{52} + 11x_{53} + 5x_{54} + 7x_{55}$\n",
    "\n",
    "Constraints:\n",
    "It must be ensured that each machine does only one of the tasks:\n",
    "\n",
    "$\\sum_j{x_{ij}} \\leq 1 \\forall i$\n",
    "\n",
    "That is:\n",
    "\n",
    "$x_{11} + x_{12} + x_{13} + x_{14} + x_{15} \\leq 1$\n",
    "\n",
    "$x_{21} + x_{22} + x_{23} + x_{24} + x_{25} \\leq 1$\n",
    "\n",
    "$x_{31} + x_{32} + x_{33} + x_{34} + x_{35} \\leq 1$\n",
    "\n",
    "$x_{41} + x_{42} + x_{43} + x_{44} + x_{45} \\leq 1$\n",
    "\n",
    "$x_{51} + x_{52} + x_{53} + x_{54} + x_{55} \\leq 1$\n",
    "\n",
    "\n",
    "We also need to ensure that all the orders are carried out:\n",
    "\n",
    "$\\sum_i{x_{ij}} \\leq 1 \\forall j$\n",
    "\n",
    "That is:\n",
    "\n",
    "$x_{11} + x_{21} + x_{31} + x_{41} + x_{51} \\geq 1$\n",
    "\n",
    "$x_{12} + x_{22} + x_{32} + x_{42} + x_{52} \\geq 1$\n",
    "\n",
    "$x_{13} + x_{23} + x_{33} + x_{43} + x_{53} \\geq 1$\n",
    "\n",
    "$x_{14} + x_{24} + x_{34} + x_{44} + x_{54} \\geq 1$\n",
    "\n",
    "$x_{15} + x_{25} + x_{35} + x_{45} + x_{55} \\geq 1$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}